#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

import random


class Solution:
    def __init__(self):
        pass

    def left_right_less_than_self(self, nums, inverse=False):
        # return list of every ele's left and right idx which less than itself
        # inverse=False: 寻找元素左右比自己小的第一个元素的索引(左边没有返回-1, 右边没有返回数组长度)
        # inverse=True : 寻找元素左右比自己大的第一个元素的索引(左边没有返回-1, 右边没有返回数组长度)
        self.nums = nums
        self.len = len(self.nums)
        self.incre_idx_stack = []       # 放的是idx
        self.left_less_idx = [None] * self.len
        self.right_less_idx = [None] * self.len

        for cur_idx in range(len(nums)):
            self.handle(cur_idx, inverse)

        for remain_idx in self.incre_idx_stack:
            # self.right_less_idx[remain_idx] = -1
            self.right_less_idx[remain_idx] = self.len

        return self.left_less_idx, self.right_less_idx

    def handle(self, cur_idx, inverse):
        stack_len = len(self.incre_idx_stack)
        cur_num = self.nums[cur_idx]

        # print('handle', cur_idx, self.incre_idx_stack)

        for i in range(stack_len-1, -1, -1):
            top_idx = self.incre_idx_stack[i]
            top_num = self.nums[top_idx]

            # print('cur_idx: ', cur_idx, cur_num, " cmp i: ", i, "top_idx:", top_idx, "top_num:", top_num)

            if (not inverse and top_num < cur_num) or (inverse and top_num > cur_num):
                # 进入时计算当前节点left: 小于当前cur_num的左边索引
                self.incre_idx_stack.append(cur_idx)
                self.left_less_idx[cur_idx] = top_idx
                break
            elif top_num == cur_num:
                # 进入时计算当前节点left: 小于当前cur_num的左边索引
                self.incre_idx_stack.append(cur_idx)
                self.left_less_idx[cur_idx] = self.left_less_idx[top_idx]
                break
            else:
                # 弹出时, 计算弹出节点right
                self.incre_idx_stack.pop()
                self.right_less_idx[top_idx] = cur_idx
        else:
            # 正常比较完栈中所有数据(都比自己小-都被弹出, 或者栈为空)
            self.incre_idx_stack.append(cur_idx)
            self.left_less_idx[cur_idx] = -1



def test():
    s = Solution()

    l = list(range(15))
    random.shuffle(l)
    # l = [1, 2, 3, 4, 5]
    # l = [4, 13, 0, 10, 8, 11, 1, 3, 9, 2, 6, 5, 7, 14, 12]
    l = [1,  2, 3, 3, 3, 4, 2]
    print(l)
    ret = s.left_right_less_than_self(l, inverse=True)
    print(ret)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
